﻿// 0814train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

/*
 grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
 */

void BFS(vector<vector<char>>& grid, queue<pair<int,int>>&oh_queue, vector<vector<bool>>&checked_grid)
{
	int row_size = grid.size();
	int col_size = grid[0].size();

	vector<vector<int>>Direction = { {-1,0},{1,0},{0,-1},{0,1} };

	while (!oh_queue.empty())
	{
		pair<int, int>top_pair = oh_queue.front();
		oh_queue.pop();

		for (auto& dir_vec : Direction)
		{
			int curr_dir_r = top_pair.first + dir_vec[0];
			int curr_dir_c = top_pair.second + dir_vec[1];

			bool is_dir_r = curr_dir_r >= 0 && curr_dir_r < row_size;
			bool is_dir_c = curr_dir_c >= 0 && curr_dir_c < col_size;

			if (is_dir_r && is_dir_c)
			{
				bool is_dir_available = grid[curr_dir_r][curr_dir_c] == '1';
				bool is_dir_visited = checked_grid[curr_dir_r][curr_dir_c];
				if (is_dir_available && !is_dir_visited)
				{
					checked_grid[curr_dir_r][curr_dir_c] = true;
					oh_queue.push(make_pair(curr_dir_r, curr_dir_c));

				}

			}
			//Direction------
		}


		//while------
	}
}

int solve01(vector<vector<char>>& grid)
{
	//1 对头队列，4个方向搜完，符合要求入队列
	//2 继续搜索队头节点
	//入队列要求 1不越界 2未访问 3grid[curr_r][curr_c]==1

	int row_size = grid.size();
	int col_size = grid[0].size();

	queue<pair<int,int>>oh_queue;

	

	vector<bool>checked_status(col_size, false);
	vector<vector<bool>>checked_grid(row_size, checked_status);

	int result = 0;
	for (int r=0; r<row_size; r++)
	{
		for (int c=0; c<col_size; c++)
		{
			bool is_available = grid[r][c] == '1';
			bool is_visited = checked_grid[r][c];
			if (is_available && !is_visited)
			{
				checked_grid[r][c] = true;
				oh_queue.push(make_pair(r,c));

				BFS(grid, oh_queue, checked_grid);

				result += 1;
				//is_available && !is_visited
			}

			//for------
		}
	}

	return result;
	//solve01
}

/*
 grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
 */

class BFS01
{
public:
	void BFS(vector<vector<int>>& grid, queue<pair<int, int>>& oh_queue, vector<vector<bool>>& checked_grid)
	{
		int row_size = grid.size();
		int col_size = grid[0].size();

		vector<vector<int>>Direction = { {-1,0},{1,0},{0,-1},{0,1} };

		while (!oh_queue.empty())
		{
			pair<int, int>top_pair = oh_queue.front();
			oh_queue.pop();

			for (auto& dir_vec : Direction)
			{
				int curr_dir_r = top_pair.first + dir_vec[0];
				int curr_dir_c = top_pair.second + dir_vec[1];

				bool is_dir_r = curr_dir_r >= 0 && curr_dir_r < row_size;
				bool is_dir_c = curr_dir_c >= 0 && curr_dir_c < col_size;

				if (is_dir_r && is_dir_c)
				{
					bool is_dir_available = grid[curr_dir_r][curr_dir_c] == 1;
					bool is_dir_visited = checked_grid[curr_dir_r][curr_dir_c];
					if (is_dir_available && !is_dir_visited)
					{
						checked_grid[curr_dir_r][curr_dir_c] = true;
						curr_count += 1;
						oh_queue.push(make_pair(curr_dir_r, curr_dir_c));

					}

				}
				//Direction------
			}


			//while------
		}
	}

	int solve01(vector<vector<int>>& grid)
	{
		//1 对头队列，4个方向搜完，符合要求入队列
		//2 继续搜索队头节点
		//入队列要求 1不越界 2未访问 3grid[curr_r][curr_c]==1

		int row_size = grid.size();
		int col_size = grid[0].size();

		queue<pair<int, int>>oh_queue;

		vector<bool>checked_status(col_size, false);
		vector<vector<bool>>checked_grid(row_size, checked_status);

		int result = 0;
		for (int r = 0; r < row_size; r++)
		{
			for (int c = 0; c < col_size; c++)
			{
				bool is_available = grid[r][c] == 1;
				bool is_visited = checked_grid[r][c];
				if (is_available && !is_visited)
				{
					checked_grid[r][c] = true;
					oh_queue.push(make_pair(r, c));
					curr_count += 1;

					BFS(grid, oh_queue, checked_grid);

					result = max(result, curr_count);
					curr_count = 0;
					//is_available && !is_visited
				}

				//for------
			}
		}

		return result;
		//solve01
	}

private:
	int curr_count = 0;
};


/*
有 n 个城市，其中一些彼此相连，另一些没有相连。
如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，
其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，
而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。

isConnected = [[1,1,0],[1,1,0],[0,0,1]] 2
 */

class BFS02
{
public:
	void BFS(vector<vector<int>>&grid, 
		queue<int>&oh_queue,
		vector<bool>&checked_vec
	)
	{
		int grid_size = grid.size();
		while (!oh_queue.empty())
		{
			int curr_index = oh_queue.front();
			oh_queue.pop();

			vector<int>curr_vec = grid[curr_index];

			for (int i=0; i< curr_vec.size(); i++)
			{
				int next_index = i;
				bool is_visited = checked_vec[next_index];
				bool is_available = curr_vec[next_index];
				if (i!=curr_index && !is_visited && is_available)
				{
					oh_queue.push(next_index);
					checked_vec[next_index] = true;
				}
			}

			//while------
		}


		//BFS----
	}

	int findCircleNum(vector<vector<int>>& isConnected) {

		//checked_vec
		//未访问 进BFS
		int grid_size = isConnected.size();
		vector<bool>checked_vec(grid_size, false);
		queue<int>oh_queue;

		int result = 0;
		for (int r=0; r<grid_size; r++)
		{
			bool is_visited = checked_vec[r];
			if (!is_visited)
			{
				oh_queue.push(r);
				checked_vec[r] = true;
				BFS(isConnected, oh_queue, checked_vec);
				result += 1;
			}
		}

		return result;
		//findCircleNum
	}

private:

	//BFS02
};


int main()
{
	{
		//isConnected = [[1,1,0],[1,1,0],[0,0,1]]
		vector<vector<int>>isConnected = { {1,1,0},{1,1,0},{0,0,1} };
		BFS02 bfs_class;
		cout << bfs_class.findCircleNum(isConnected);

		return 0;
	}

	{
		vector<int>vec1 = { 0,0,1,0,0,0,0,1,0,0,0,0,0 };
		vector<int>vec2 = { 0,0,0,0,0,0,0,1,1,1,0,0,0 };
		vector<int>vec3 = { 0,1,1,0,1,0,0,0,0,0,0,0,0 };
		vector<int>vec4 = { 0,1,0,0,1,1,0,0,1,0,1,0,0 };
		vector<int>vec5 = { 0,1,0,0,1,1,0,0,1,1,1,0,0 };
		vector<int>vec6 = { 0,0,0,0,0,0,0,0,0,0,1,0,0 };
		vector<int>vec7 = { 0,0,0,0,0,0,0,1,1,1,0,0,0 };
		vector<int>vec8 = { 0,0,0,0,0,0,0,1,1,0,0,0,0 };
		vector<vector<int>>grid = { vec1,vec2,vec3,vec4, vec5,vec6,vec7,vec8 };

		BFS01 bfs_class;
		cout << bfs_class.solve01(grid);


		return 0;
	}


	vector<char>vec1 = {'1','1','1','1','0'};
	vector<char>vec2 = {'1','1','0','1','0'};
	vector<char>vec3 = {'1','1','0','0','0'};
	vector<char>vec4 = {'0','0','0','0','0'};

	vector<vector<char>>grid = { vec1 ,vec2,vec3,vec4 };

	cout << solve01(grid);
	//main------
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
